Calcul de compléxité, pour quoi faire?

Nous allons dans cette partie introduire la notion de complexité algorithmique, sorte de quantification de la performance d'un algorithme.

L'objectif premier d'un calcul de complexité algorithmique est de pouvoir comparer l’efficacité d’algorithmes résolvant le même problème. Dans une situation donnée, cela permet donc d'établir lequel des algorithmes disponibles est le plus optimal.

Ce type de question est primordial, car pour des données volumineuses la différence entre les durées d'exécution de deux algorithmes ayant la même finalité peut être de l'ordre de plusieurs jours.

Les règles que nous utiliserons pour comparer et évaluer les algorithmes devront respecter certaines contraintes très naturelles. On requerra principalement qu'elles ne soient pas tributaires des qualités d'une machine ou d'un choix de technologie.

Nous allons donc effectuer des calculs sur l’algorithme en lui même, dans sa version "papier". Les résultats de ces calculs fourniront une estimation du temps d’exécution de l’algorithme, et de la taille mémoire occupée lors de son fonctionnement.

Calcul de complexité.

Règles générales

Pour calculer la compléxité, nous allons devoir examiner chaque ligne de code et l'y attribuer un coût en temps.

Le coût ainsi obtenu n'aura pas d'unité, il s'agit d'un nombre d'opérations dont chacune aurait le même temps déexecution :1.

Les opérations qui vont devoir être comptabilisées sont :

Déterminons le coût de la ligne de code suivante :
a←a+1
$T(n)=1 $(affectation)$+1$(accés à la mémoire $a$)$+1$(addition)$=3$

Algorithmes sans structure de contrôle

Déterminer le complexité T(n) de cette algorithme écrit en python. 
1 def conversion(n:float)->lst:
2	h = n // 3600
3	m = (n - 3600*h) // 60
4	s = n % 60
5	return h,m,s
On ne comptera pas la ligne 1 et 5. Dans la suite quand on s'intéressera à la compléxité d'un algo écrit en Python nous ne préterons pas attention à la ligne de définition de la fonction et au return.

Algorithmes avec structure conditionnelle.

La fonction suivante calcule $(-1)^n$ sans effectuer de produit mais en utilisant un test avec une alternative : 
1 def puissanceMoinsUn(n:int)->int:
2 	if n%2==0:
3 		res = 1
4 	else:
5 		res = -1
6	return res
Déterminer le complexité $T(n)$ de cette algorithme

Algorithmes avec structure itérative.

Cette fonction utilise une structure for pour calculer la somme des $n$ premiers entiers 
1 def sommeEntiers(n):
2 	somme = 0
3 	for i in range(n+1):
4 		somme += i
5 	return somme
Déterminer le complexité T(n) de cette algorithme.

La compléxité de cette algorithme est dite linéaire. Ce sera le cas de tous les algorithmes avec $T(n)=an+b$ où $a$ et $b$ sont des réels.

Algorithmes avec deux structures itératives imbriquées.

1 def trouvemot(mots:lst, fichier_test:lst)->lst:
2 	resultat=[]
3 	for mot in mots:
4 		for ligne in fichier_test:
5 			if mot in ligne:
6				resultat.append(mot)
7	return resultat
Déterminer le complexité $T(n)$ de cette algorithme en considérant que la taille des listes mots et fichiers_test sont de $n$.

La compléxité de cette algorithme est dite quadratique. Ce sera le cas de tous les algorithmes avec $T(n)=an^2+bn+c$ où $a$, $b$ et $c$ sont des réels.

La complexité algorithmique est une notion qui peut être plus complexe que ce que nous venons de voir, nous n'irons pas plus loin dans le programme de première. Nous retravaillerons cette notion notament sur la séquence A3.

Sitographie

Voici une liste de sites traitant de la complexité :

Savoir faire et Savoir